A linked list is a data structure that contains a list of data items. Each item, referred to as a node, includes a link to the next item in the list. The linked list itself may be referred to simply by providing a pointer to the first and/or last node of the list, allowing the linked list to be traversed in either direction. An array list is generally a list of items in a contiguous portion of storage. Access to an item in the array list may be obtained by simply specifying an offset for the item from the beginning of the list providing random access to the item. Choosing between a linked list versus an array list is a usual dilemma in the implementation phase of any application that needs to deal with considerable amounts of data. Each type of list has its pros as well as cons, but choosing one over the other inevitably leads to a set of scenarios where the implementation compromises on performance.
The Java Platform, Standard Edition provides ArrayList and LinkedList as part of its java.util package for developers' convenience. The difference in performance between the two are negligible when working with lists of small size (of the order of a few hundreds), but as the size increases, it becomes more and more prominent.
ArrayLists use an internal array to store the list data. Arrays provide the best performance for random access, as the address of every element can be calculated by adding an offset to the base address of the array. This makes finding the address of the nth item or element in the list as easy as base_address+(n*size of element). But this creates another problem—every element must be put in consecutive memory locations without any gaps in between. Insertion and deletion of elements becomes extremely expensive as a result. If, for example, an array has 100 elements, to insert an element in index 0, 100 elements will be relocated one position to the right internally in the memory. The same goes for deletion, with every succeeding element being shifted one position to the left. ArrayList also suffers when the internal array is completely full, and therefore have to create a bigger array and reallocate all the elements.
LinkedLists do not have the constraint that they should be arranged sequentially in the memory. Each node in LinkedList contains a pointer or reference to the memory location of the next node in the list. Hence, the nodes may be completely scattered in memory, and the list will still be functional. This also saves the hassle of having to find contiguous blocks of free space in the memory to allocate to the list. The primary advantage of this design has to do with insertion and deletion of items in the list. Inserting a new item in the list is simply a matter of changing the pointer of the previous node to point to the new node, and assigning the pointer in the new node to point to the next node. Similarly, deletion also requires only changing one pointer. This gives insertion/deletion a constant time complexity of O(1). The tradeoff, however, is in random access. To access the nth node in a list, one will have to traverse through n−1 nodes before that node (since the LinkedList maintains only pointers to head and the tail of the list, and nowhere in between). Size wise, LinkedList will occupy more space since each node will have two additional pointer references in it (to the previous node, and the next node).